package MonthGame.problem5;

import java.math.BigInteger;
import java.util.Scanner;

public class Password {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int t = s.nextInt();
        for(int i=0;i<t;i++){
            int p = s.nextInt();
            BigInteger ans = new BigInteger("0");
            for(int j=1;j<p;j++){
                int temp = 0;
                ans = ans.add(new BigInteger(String.valueOf(Function(j,p,temp))));
            }System.out.println(ans);
        }
    }

    static int Function(int x,int p,int temp){
        if(x<=1){
            return ++temp;
        };
        ++temp;
        temp = Function(p%x,p,temp);
        return temp;
    }
}
